package lhc.alg.top100;

/**
 * description:
 * 模拟
 * author: hongchen.liao
 * date:  2022/9/5
 */
public class _86_Partition_List {


    //Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    class Solution {
        public ListNode partition(ListNode head, int x) {
            ListNode samll = new ListNode(0);
            ListNode samllHead = samll;
            ListNode large = new ListNode(0);
            ListNode largeHead = large;
            while(head != null){
                if(head.val < x){
                    samll.next = head;
                    samll = samll.next;
                }else{
                    large.next = head;
                    large = large.next;
                }
                head = head.next;
            }
            large.next = null;
            samll.next = largeHead.next;
            return samllHead.next;
        }
    }

}
